//
// Created by liyf on 2021/6/8.
//

#include "ALGraph.h"

GraphAdjList * AdInit(char * points, char edges [][3],int eSz){
    GraphAdjList * graph = malloc(sizeof(GraphAdjList) + sizeof(VertexNode) * MAXVEX);
    graph->vSz = 0;
    graph->eSz = 0;
    //初始化点数组
    VertexNode **list = malloc(sizeof(VertexNode*) * MAXVEX);
    for(int i = 0; i < MAXVEX; i++){
        list[i] = malloc(sizeof(VertexNode));
        memset(list[i],0,sizeof(VertexNode));
    }
    graph->adjlist = list;
    //添加点
    for(int i = 0; points[i] != '\0'; i++){
        list[i]->value = points[i];
        graph->vSz++;
    }
    //添加边
    for(int i = 0; i < eSz; i++){
        //找点坐标
        int from = -1;
        int to = -1;
        for(int j = 0; j < graph->vSz; j++){
            if(edges[i][0] == list[j]->value)
                from = j;
            if(edges[i][1] == list[j]->value)
                to = j;
        }
        if(from == -1 || to == -1)
            continue;  //没找到

        //初始化EdgeNode
        EdgeNode * edgeNode = malloc(sizeof(EdgeNode));
        edgeNode->adjvex = to;
        edgeNode->weight = edges[i][2] - '0';
        edgeNode->next = NULL;
        //对应点的入度增加
        list[to]->in++;

        //添加链表操作
        EdgeNode * cur = list[from]->firstEdge;
        if(cur){
            while(cur->next)
                cur = cur->next;
            cur->next = edgeNode;
        } else {
            list[from]->firstEdge = edgeNode;
        }
    }

    return graph;
}

typedef struct Queue{
    int head;
    int sz;
    int arr[100];
} Queue;
void GraphAdPrint(GraphAdjList * graph){
    VertexNode ** list = graph->adjlist;
    for(int i = 0; i < graph->vSz;i++){
        printf("%2d %d %c",i,list[i]->in,list[i]->value);
        EdgeNode * cur = list[i]->firstEdge;
        while(cur){
            printf("->%c",list[cur->adjvex]->value);
            cur = cur->next;
        }
        printf("\n");
    }
}
void DFSTraverse(GraphAdjList * graph){
    Queue queue;    //记录
    memset(queue.arr,0,sizeof(int) * 100);
    queue.sz = 0;
    //已访问数组
    int * vistited = malloc(sizeof(int) * graph->vSz);
    memset(vistited,0, sizeof(int) * graph->vSz);
    VertexNode ** list = graph->adjlist;
    int i = 0;

    while(1){
        if(vistited[i] == 0)
            printf("%c->", list[i]->value);
        vistited[i] = 1;

        EdgeNode* cur = list[i]->firstEdge;
        if(cur){
            while(cur){
                int j = cur->adjvex;
                if(vistited[j] == 0){
                    queue.arr[queue.sz++] = i;
                    i = j;
                    break;
                }
                if(cur->next == NULL){
                    i = queue.arr[queue.sz--];
                    break;
                }
                cur = cur->next;
            }
        } else{
            i = queue.arr[queue.sz--];
        }

        for(int j = 0; j < graph->vSz; j++){
            if(vistited[j] == 0)
                break;
            if(j == graph->vSz - 1){
                printf("\n");
                return;
            }
        }
    }
}
void BFSTraverse(GraphAdjList * graph){
    //是否访问数组
    int * visited = malloc(sizeof(int) * graph->vSz);
    memset(visited, 0 , sizeof(int) * graph->vSz);

    //初始化队列
    Queue * queue = malloc(sizeof(Queue) + sizeof(int) * 10);
    queue->sz = 0;
    queue->head = 0;
    memset(queue->arr,0,sizeof(int) * 10);

    for(int i = 0; i < graph->vSz; i++){
        VertexNode * cur = graph->adjlist[i];
        if(cur){
            queue->arr[queue->sz++] = i;
            break;
        } else {
            i++;
        }
    }
    VertexNode ** list = graph->adjlist;
    while(queue->sz > queue->head){
        int lastSz  = queue->sz;
        while(lastSz > queue->head){
            int index = queue->arr[queue->head++];
            VertexNode * p = list[index];
            //输出
            if(visited[index] == 0){
                printf("%c->",p->value);
            }
            visited[index] = 1;
            //添加到队列
            EdgeNode * cur = p->firstEdge;
            while(cur){
                if(visited[cur->adjvex] == 0)
                    queue->arr[queue->sz++] = cur->adjvex;
                cur = cur->next;
            }
        }
    }
    printf("\n");
}
//关键路径需要用到的参数
typedef struct Stack{
    int sz;
    int arr[];
} Stack;
Stack * sPrint;
int * etv;
void TopologicalSort(GraphAdjList * graph){
    //参数准备
    int vSz = graph->vSz;
    VertexNode ** list = graph->adjlist;
    //初始化
    //拓扑排序功能栈
    Stack * stack = malloc(sizeof(Stack) + sizeof(int) * vSz);
    memset(stack,0,sizeof(Stack) + sizeof(int) * vSz);
    //已访问数组
    int * visited = malloc(sizeof(int) * vSz);
    memset(visited,0,sizeof(int) * vSz);
    //已输出数量
    int count = 0;
    //事件最早发生事件数组
    etv = malloc(sizeof(int) * vSz);
    memset(etv,0,sizeof(int) * vSz);
    //输出栈
    sPrint = malloc(sizeof(Stack) + sizeof(int) * vSz);
    memset(sPrint, 0, sizeof(int) * vSz);
    //执行算法
    while(vSz > count){
        //找出入度为0的点
        for(int i = 0; i < vSz; i++){
            if(list[i]->in == 0 && (visited[i] == 0)){
                stack->arr[++stack->sz] = i;
                visited[i] = 1;
            }
        }
        //打印栈顶部
        int pIndex = stack->arr[stack->sz--];
        //输出
        printf("%c->",list[pIndex]->value);
        sPrint->arr[sPrint->sz++] = pIndex;
        count++;
        //断开边链表（不能真的断开，因为没有备份）
        EdgeNode * cur = list[pIndex]->firstEdge;
        while(cur){ //让连接到的点入度减少
            list[cur->adjvex]->in -- ;

            //求各顶点事件发生最早时间点
            int adjvex = cur->adjvex;   //当前边指向的下标
            if((etv[pIndex] + cur->weight) > etv[adjvex]){
                etv[adjvex] = etv[pIndex] + cur->weight;
            }

            cur = cur->next;
        }
    }
    printf("\n");


}
void CriticalPath(GraphAdjList * graph){
    //参数
    int vSz = graph->vSz;
    VertexNode ** list = graph->adjlist;
    TopologicalSort(graph);
    //初始化
    //事件最晚发生时间
    int * ltv = malloc(sizeof(int) * vSz);
    for(int i = 0; i < vSz; i++)
        ltv[i] = etv[vSz-1];    //赋值为最早发生时间的最后一位

    //计算ltv
    while(sPrint->sz != 0){
        //拓扑序列出栈
        int pIndex = sPrint->arr[--sPrint->sz];
        for(EdgeNode * cur = list[pIndex]->firstEdge; cur; cur = cur->next){
            //求各个顶点事件最迟发生事件ltv值
            int adjvex = cur->adjvex;   //当前节点指向的下标
            if(ltv[adjvex] - cur->weight < ltv[pIndex]){
                ltv[pIndex] = ltv[adjvex] - cur->weight;
            }
        }
    }
    //求ete,lte和关键活动
    for(int i = 0; i < vSz; i++){
        for(EdgeNode * cur = list[i]->firstEdge; cur; cur = cur->next){
            int adjvex = cur->adjvex;
            int ete = etv[i];   //活动最早发生的时间
            int lte = ltv[adjvex] - cur->weight;    //活动最迟发生的时间
            if(ete == lte){ //相等即在关键路径上
                printf("%c>-%d->",list[i]->value,cur->weight);
            }
        }
    }
    //输出
    printf("\n%6s"," ");
    for(int i = 0 ; i < vSz; i++){
        printf("%2d ", i);
    }
    printf("\n%6s","etv:");
    for(int i = 0; i < vSz; i++){
        printf("%2d ", etv[i]);
    }
    printf("\n%6s","ltv:");
    for(int i = 0; i < vSz; i++){
        printf("%2d ",ltv[i]);
    }
    printf("\n%6s","stack:");
    for(int i = 0; i < vSz; i++){
        printf("%2d ", sPrint->arr[i]);
    }
}